package stru1.day4;

import java.util.ArrayList;
import java.util.List;

/**
 * 118. 杨辉三角
 */
public class Solution2 {
    public static void main(String[] args) {
        System.out.println(generate(5));
        System.out.println(generate(1));
    }

    /**
     * 更具性质 res[i][j] = res[i-1][j-1]+res[i-1][j]可递推求出
     * 这里杨辉三角每行的长度是确定的，我们可以在list实例化的时候指定初始化长度，来节省内存的不必要消耗
     */
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>(numRows);
        //第一行
        ArrayList<Integer> first = new ArrayList<>(1);
        first.add(1);
        res.add(first);

        List<Integer> temp;
        for (int i = 1; i < numRows; i++) {
            temp = new ArrayList<>(i + 1);
            temp.add(1); //每行开头元素
            for (int j = 1; j < i; j++) {
                List<Integer> pre = res.get(i - 1);
                temp.add(pre.get(j - 1) + pre.get(j));
            }
            temp.add(1); //每行结尾元素
            res.add(temp);
        }

        return res;
    }
}
